package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/merge-two-sorted-lists/
 *  合并两个有序链表   搞一个虚节点
 * author: hongchen.liao
 * date:  2022/9/20
 */
public class _21_ {


     //Definition for singly-linked list.
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode p = dummy;
            ListNode l1 = list1, l2 = list2;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    p.next = l1;
                    l1 = l1.next;
                }else{
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
            p.next = l1 != null ? l1 : l2;
            return dummy.next;
        }
    }


}
